//
// Created by sjjmw on 1/21/2022.
//
#include "base.h"

//节点数不超过 100 。
//每个节点值Node.val 都是唯一的，1 <= Node.val <= 100。
//无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
//由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p的邻居。
//图是连通图，你可以从给定节点访问到所有节点。


// Definition for a Node.
class Node {
public:
    int val;
    vector<Node *> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node *>();
    }

    Node(int _val) {
        val = _val;
        neighbors = vector<Node *>();
    }

    Node(int _val, vector<Node *> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};


class Solution {
public:
//    bool visited[100] = {false};
    Node* visited[101] = {nullptr};

    Node *clone_recur(Node *node) {
        //节点已经创建
        if(visited[node->val]){
            return visited[node->val];
        }
        visited[node->val]=new Node(node->val);
//        visited[node->val]->neighbors.resize(node->neighbors.size());
        for (auto& a:node->neighbors) {
            visited[node->val]->neighbors.push_back(clone_recur(a));
        }
        return visited[node->val];
    }

    Node *cloneGraph(Node *node) {
        if(node== nullptr){
            return nullptr;
        }
        return clone_recur(node);
    }
};

Node* gen_graph(vector<vector<int>> nodes_con){
    unordered_map<int,Node*> map;
    //创建nodes
    for (int i = 0; i < nodes_con.size(); ++i) {
        map[i+1]=new Node(i+1);
    }
    //加入neighbor
    for (int i = 0; i < nodes_con.size(); ++i) {
        for(auto nb_id:nodes_con[i]){
            map.at(i+1)->neighbors.push_back(map.at(nb_id));
        }
    }
    return map.begin()->second;
}

int main(){
    Solution sol;
    vector<vector<int>> vec={{2,4},{1,3},{2,4},{1,3}};
    auto g1=gen_graph(vec);
    auto g2=sol.cloneGraph(g1);
    return 0;
}